import { ListNode, TreeNode } from '../DataStructure'

function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
  let flag = false

  function match(head?: ListNode, root?: TreeNode) {
    if (head?.val !== root?.val) {
      return
    }
    if (head.next) {
      root?.left && match(head.next, root?.left)
      root?.right && match(head.next, root?.right)
    } else {
      flag = true
    }

  }

  function traversal(tree: TreeNode) {
    match(head, tree)
    tree.left && traversal(tree.left)
    tree.right && traversal(tree.right)
  }

  traversal(root)
  return flag
}

export default function () {
  const root = new TreeNode(
    1,
    new TreeNode(
      4,
      null,
      new TreeNode(
        2,
        new TreeNode(1),
        null
      )
    ),
    new TreeNode(
      4,
      new TreeNode(
        2,
        new TreeNode(6),
        new TreeNode(
          8,
          new TreeNode(1),
          new TreeNode(3)
        )
      ),
      null
    )
  )
  console.log('case1', isSubPath(new ListNode(4, new ListNode(2, new ListNode(8))), root))
  console.log('case2', isSubPath(new ListNode(1, new ListNode(4, new ListNode(2, new ListNode(6)))), root))
  console.log('case3', isSubPath(new ListNode(1, new ListNode(4, new ListNode(2, new ListNode(6, new ListNode(8))))), root))
  const root2 = new TreeNode(1, null, new TreeNode(
    1,
    new TreeNode(10, new TreeNode(9)),
    new TreeNode(1)
  ))
  console.log('case4', isSubPath(new ListNode(1, new ListNode(10)), root2))
}
